package com.gxc.rapacity;

import java.util.PriorityQueue;

/**
 * 一块金条切成两半，是需要花费和长度数值一样的铜板的。
 * 比如长度为20的金条，不管切成长度多大的两半，都要花费20个铜板。
 一群人想整分整块金条，怎么分最省铜板?
 例如,给定数组[10,20,30]，代表一共三个人，整块金条长度为10+20+30=60。
 金条要分成10,20,30三个部分。
 如果先把长度60的金条分成10和50，花费60;
 再把长度50的金条分成20和30，花费50;一
 共花费110铜板。
 但是如果先把长度60的金条分成30和30，花费60:
 再把长度30金条分成10和20花费30;
 一共花费90铜板。
 输入一个数组，返回分割的最小代价。

 哈夫曼树
 */
public class HuffmanTree {

    public static void main(String[] args) {
        int[] a = {2, 3, 4, 7, 9, 2};

        int result = huffmanTree(a);
        System.out.println(result);

        result = huffmanTree2(a);
        System.out.println(result);
    }

    private static int huffmanTree2(int[] a) {
        //建立一个小跟堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i : a) {
            priorityQueue.add(i);
        }

        //一次弹出两个数，两个数相加之和丢回小跟堆
        int sum = 0;
        while (priorityQueue.size()>1) {
            sum = priorityQueue.poll() + priorityQueue.poll();
            priorityQueue.add(sum);
        }
        return sum;
    }

    private static int huffmanTree(int[] a) {
        //建立一个小跟堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i : a) {
            priorityQueue.add(i);
        }

        //一次弹出两个数，两个数相加之和丢回小跟堆
        int sum = 0;
        while (!priorityQueue.isEmpty()) {
            Integer min = priorityQueue.poll();
            if (!priorityQueue.isEmpty()) {
                Integer min2 = priorityQueue.poll();
                sum = min + min2;
                priorityQueue.add(sum);
            }
            sum = min;
        }
        return sum;
    }


}
